JZ6 旋转数组的最小数字

这题主要考察二分算法变种，老实说还是挺难的，主要就是各种健壮性判断，以及对于递增数组和递减数组应该怎么处理

https://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba

第一次解：

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        int low = 0;
        int high = array.length - 1;
        while(low < high) {
            // 之所以不用 (high - low) / 2 是为了避免出现负的下标
            int mid = low + (high - low) / 2;
            /// 说明mid所在的位置是在第一个非递减子数组中
            if(array[mid] > array[high]) {
                low = mid + 1;
            }
            /// 
            else if(array[mid] == array[high]) {
                high = high - 1;
            }
            else {
                high = mid;
            }
        }
        
        return array[low];
    }
}

这个写法和第二次解是一样的，不过第二次写的更直观点

第二次解：

参考题解：https://blog.nowcoder.net/n/dcb0f2e6ffd44e1895b7a5297e362778?f=comment

4,5,1,2,3

import java.util.ArrayList;

public class Solution {
    public int minNumberInRotateArray(int [] array) {
        if (array == null || array.length == 0) return 0;
        // 要求时间复杂度为 logn 那就只能二分了
        int high = array.length - 1;
        int low = 0;
        while (low < high) {
            // 子数组是非递减的数组，10111
            if (array[low] < array[high]) return array[low];
            int mid = low + (high - low) / 2;
            // mid 位于左半边
            if (array[mid] > array[low]) low = mid + 1;
            // mid 位于右半边
            else if (array[mid] < array[high]) high = mid;
            // 其它情况，非递增左半边右半边都无法判断为有序，所以需要缩小范围
            else low++;
        }
        return array[low];
    }
}

如果待查询的范围最后只剩两个数，那么 mid 一定会指向下标靠前的数字，所以令 low++

23-5-23

这题的关键是理解，下面这个

if (array[low] < array[high]) return array[low];

当低位指针小于高位指针时，说明这个数组是递增的，那么最小值就是低位指针的值

func minNumberInRotateArray(rotateArray []int) int {
    if len(rotateArray) == 0 {
        return 0
    }

    low, high := 0, len(rotateArray)-1
    for low < high {
        mid := (high-low)/2 + low
        if rotateArray[low] < rotateArray[high] {
            return rotateArray[low]
        } else if rotateArray[mid] > rotateArray[low] {
            low = mid
        } else if rotateArray[mid] < rotateArray[high] {
            high = mid
        } else {
            low++
        }
    }
    return rotateArray[low]
}